//52.N皇后II
//https://leetcode.cn/problems/n-queens-ii/
class Solution {
    //列,左斜,右斜
    unordered_set<int> col, diag1, diag2;
public:
    int totalNQueens(int n) { return backtrack(n, 0); }

    //回溯
    int backtrack(int n, int row) {
        if (row == n) return 1;

        int count = 0;
        //每一行依次在该列放入一个皇后
        for (int i = 0; i < n; i++) {
            //查询该列是否有皇后
            if (col.find(i) != col.end()) continue;

            //同一左斜中每一格 行-列 都相等
            //查询左斜有没有皇后
            int diagnum1 = row - i; //行-列得到左斜
            if (diag1.find(diagnum1) != diag1.end()) continue;

            //同一右斜中每一格 行+列 都相等
            //查询右斜有没有皇后
            int diagnum2 = row + i; //行+列得到右斜
            if (diag2.find(diagnum2) != diag2.end()) continue;

            //如果都可以则在该列和左右斜边的集合中加入该皇后
            col.insert(i);
            diag1.insert(diagnum1);
            diag2.insert(diagnum2);

            //继续遍历放置其他皇后
            count += backtrack(n, row + 1);

            //删除该皇后的痕迹
            col.erase(i);
            diag1.erase(diagnum1);
            diag2.erase(diagnum2);
        }
        return count;
    }
};